#include <iostream>
#include <vector>
#include <cstdlib>       // for srand and rand
#include <ctime>        // for time
#include <algorithm>    // for swap
using namespace std;

/*
* 快速排序算法实现 
*/

#define ElemType int
#define ElemNum 10
#define DEBUG

int Partition(vector<ElemType>& arr, int left, int right) {
    // 1、随机选取枢轴值
    // ElemType pivot = arr[low]; 
    // 如果每次都以第一个元素作为枢轴元素，会有一个问题
    // 即数组有序的话，算法效率会很差，所以可以改为随机选取枢轴元素
    // 不过随机选取之后需要和第一个元素做交换
    int pivot_pos = rand() % (right - left + 1) + left;
    // (right - left + 1) 确定 left 到 right 这个范围内的元素个数
    // 然后+left表示进行偏移
    // 比如 rand()%100 表示 随机生成 0~99 的随机数，随机数的个数是100，范围是[0,99]
    // 而 rand()%(right-left+1) 表示 随机生成 0~right-left 的随机数，随机数的个数是right-left+1，范围是[0,right-left]
    // 然后+left进行偏移，即范围变成[left,right]
    swap(arr[left], arr[pivot_pos]);
    ElemType pivot = arr[left];

    #ifdef DEBUG
    cout << "pivot_pos = " << pivot_pos << " pivot = " << pivot << endl;
    #endif

    // 2、开始划分，小于枢轴值的元素放到左边，大于的放到右边
    while (left < right) {
        while (left < right && arr[right] >= pivot) --right;
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) ++left;
        arr[right] = arr[left];
    }

    arr[left] = pivot;
    return left;
}

void QuickSort(vector<ElemType>& arr, int left, int right) {
    if (left < right) { // 递归跳出的条件 相等或者大于都跳出
        int pivot_pos = Partition(arr, left, right); // 划分，已经确定一个元素的最终位置
        QuickSort(arr, left, pivot_pos - 1);
        QuickSort(arr, pivot_pos + 1, right);
    }
}

void Print(const vector<ElemType>& arr) {
    for (const ElemType& elem : arr) {
        cout << elem << " ";
    }
    cout << endl << endl;
}

int main(void) {
    // 设置随机数种子
    srand(time(0));

    // 随机生成测试用例
    vector<ElemType> arr(ElemNum);
    for (int i = 0; i < ElemNum; ++i) {
        arr[i] = rand() % 100 + 1; // 随机生成 1~100 随机数
    }

    cout << "排序前：" << endl;
    Print(arr);
    
    QuickSort(arr, 0, arr.size() - 1);

    cout << "排序后：" << endl;
    Print(arr);

    return 0;
}

// g++ -o quick_sort quick_sort.cc